/*
 * MOAB, a Mesh-Oriented datABase, is a software component for creating,
 * storing and accessing finite element mesh data.
 *
 * Copyright 2004 Sandia Corporation.  Under the terms of Contract
 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
 * retains certain rights in this software.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 */

/**\file MeshSetSequence.cpp
 *\author Jason Kraftcheck (kraftche@cae.wisc.edu)
 *\date 2007-04-30
 */

#include "MeshSetSequence.hpp"
#include "SequenceManager.hpp"

namespace moab
{

MeshSetSequence::MeshSetSequence( EntityHandle start, EntityID count, const unsigned* flags, SequenceData* dat )
    : EntitySequence( start, count, dat )
{
    initialize( flags );
}

MeshSetSequence::MeshSetSequence( EntityHandle start, EntityID count, unsigned flags, SequenceData* dat )
    : EntitySequence( start, count, dat )
{
    std::vector< unsigned > vect( count, flags );
    initialize( &vect[0] );
}

MeshSetSequence::MeshSetSequence( EntityHandle start, EntityID count, const unsigned* flags, EntityID data_size )
    : EntitySequence( start, count, new SequenceData( 1, start, start + data_size - 1 ) )
{
    initialize( flags );
}

MeshSetSequence::MeshSetSequence( EntityHandle start, EntityID count, unsigned flags, EntityID data_size )
    : EntitySequence( start, count, new SequenceData( 1, start, start + data_size - 1 ) )
{
    std::vector< unsigned > vect( count, flags );
    initialize( &vect[0] );
}

void MeshSetSequence::initialize( const unsigned* flags )
{
    if( !data()->get_sequence_data( 0 ) ) data()->create_sequence_data( 0, SET_SIZE );

    EntityID offset = start_handle() - data()->start_handle();
    for( EntityID i = 0; i < size(); ++i )
        allocate_set( flags[i], i + offset );
}

MeshSetSequence::~MeshSetSequence()
{
    EntityID offset = start_handle() - data()->start_handle();
    EntityID count  = size();
    for( EntityID i = 0; i < count; ++i )
        deallocate_set( i + offset );
}

EntitySequence* MeshSetSequence::split( EntityHandle here )
{
    return new MeshSetSequence( *this, here );
}

ErrorCode MeshSetSequence::pop_back( EntityID count )
{
    EntityID offset = end_handle() + 1 - count - data()->start_handle();
    ErrorCode rval  = EntitySequence::pop_back( count );
    if( MB_SUCCESS == rval )
        for( EntityID i = 0; i < count; ++i )
            deallocate_set( i + offset );
    return rval;
}

ErrorCode MeshSetSequence::pop_front( EntityID count )
{
    EntityID offset = start_handle() - data()->start_handle();
    ErrorCode rval  = EntitySequence::pop_front( count );
    if( MB_SUCCESS == rval )
        for( EntityID i = 0; i < count; ++i )
            deallocate_set( i + offset );
    return rval;
}

ErrorCode MeshSetSequence::push_back( EntityID count, const unsigned* flags )
{
    EntityID offset = end_handle() + 1 - data()->start_handle();
    ErrorCode rval  = EntitySequence::append_entities( count );
    if( MB_SUCCESS == rval )
        for( EntityID i = 0; i < count; ++i )
            allocate_set( flags[i], i + offset );
    return rval;
}

ErrorCode MeshSetSequence::push_front( EntityID count, const unsigned* flags )
{
    EntityID offset = start_handle() - data()->start_handle() - count;
    ErrorCode rval  = EntitySequence::prepend_entities( count );
    if( MB_SUCCESS == rval )
        for( EntityID i = 0; i < count; ++i )
            allocate_set( flags[i], i + offset );
    return rval;
}

void MeshSetSequence::get_const_memory_use( unsigned long& per_ent, unsigned long& seq_size ) const
{
    per_ent  = SET_SIZE;
    seq_size = sizeof( *this );
}

unsigned long MeshSetSequence::get_per_entity_memory_use( EntityHandle first, EntityHandle last ) const
{
    if( first < start_handle() ) first = start_handle();
    if( last > end_handle() ) last = end_handle();

    unsigned long sum = 0;
    for( EntityHandle h = first; h <= last; ++h )
        sum += get_set( h )->get_memory_use();
    return sum;
}

ErrorCode MeshSetSequence::get_entities( const SequenceManager* seqman,
                                         EntityHandle handle,
                                         Range& entities,
                                         bool recursive ) const
{
    if( !recursive )
    {
        get_set( handle )->get_entities( entities );
        return MB_SUCCESS;
    }
    else
    {
        std::vector< const MeshSet* > list;
        ErrorCode rval = recursive_get_sets( handle, seqman, &list );
        for( std::vector< const MeshSet* >::iterator i = list.begin(); i != list.end(); ++i )
            ( *i )->get_non_set_entities( entities );
        return rval;
    }
}

ErrorCode MeshSetSequence::get_entities( EntityHandle handle, std::vector< EntityHandle >& entities ) const
{
    get_set( handle )->get_entities( entities );
    return MB_SUCCESS;
}

ErrorCode MeshSetSequence::get_dimension( const SequenceManager* seqman,
                                          EntityHandle handle,
                                          int dimension,
                                          std::vector< EntityHandle >& entities,
                                          bool recursive ) const
{
    if( !recursive )
    {
        get_set( handle )->get_entities_by_dimension( dimension, entities );
        return MB_SUCCESS;
    }
    else
    {
        std::vector< const MeshSet* > list;
        ErrorCode rval = recursive_get_sets( handle, seqman, &list );
        for( std::vector< const MeshSet* >::iterator i = list.begin(); i != list.end(); ++i )
            ( *i )->get_entities_by_dimension( dimension, entities );
        return rval;
    }
}

ErrorCode MeshSetSequence::get_dimension( const SequenceManager* seqman,
                                          EntityHandle handle,
                                          int dimension,
                                          Range& entities,
                                          bool recursive ) const
{
    if( !recursive )
    {
        get_set( handle )->get_entities_by_dimension( dimension, entities );
        return MB_SUCCESS;
    }
    else
    {
        std::vector< const MeshSet* > list;
        ErrorCode rval = recursive_get_sets( handle, seqman, &list );
        for( std::vector< const MeshSet* >::iterator i = list.begin(); i != list.end(); ++i )
            ( *i )->get_entities_by_dimension( dimension, entities );
        return rval;
    }
}

ErrorCode MeshSetSequence::get_type( const SequenceManager* seqman,
                                     EntityHandle handle,
                                     EntityType tp,
                                     std::vector< EntityHandle >& entities,
                                     bool recursive ) const
{
    if( !recursive )
    {
        get_set( handle )->get_entities_by_type( tp, entities );
        return MB_SUCCESS;
    }
    else if( tp == MBENTITYSET )
    {
        return recursive_get_sets( handle, seqman, 0, 0, &entities );
    }
    else if( tp == MBMAXTYPE )
    {
        Range tmp;
        ErrorCode rval = get_entities( seqman, handle, tmp, recursive );
        if( MB_SUCCESS == rval )
        {
#ifdef MOAB_NO_VECTOR_TEMPLATE_INSERT
            std::copy( tmp.begin(), tmp.end(), std::back_inserter( entities ) );
#else
            entities.insert( entities.end(), tmp.begin(), tmp.end() );
#endif
        }
        return rval;
    }
    else
    {
        std::vector< const MeshSet* > list;
        ErrorCode rval = recursive_get_sets( handle, seqman, &list );
        for( std::vector< const MeshSet* >::iterator i = list.begin(); i != list.end(); ++i )
            ( *i )->get_entities_by_type( tp, entities );
        return rval;
    }
}

ErrorCode MeshSetSequence::get_type( const SequenceManager* seqman,
                                     EntityHandle handle,
                                     EntityType tp,
                                     Range& entities,
                                     bool recursive ) const
{
    if( !recursive )
    {
        get_set( handle )->get_entities_by_type( tp, entities );
        return MB_SUCCESS;
    }
    else if( tp == MBENTITYSET )
    {
        return recursive_get_sets( handle, seqman, 0, &entities );
    }
    else if( tp == MBMAXTYPE )
    {
        std::vector< const MeshSet* > list;
        ErrorCode rval = recursive_get_sets( handle, seqman, &list );
        for( std::vector< const MeshSet* >::iterator i = list.begin(); i != list.end(); ++i )
            ( *i )->get_non_set_entities( entities );
        return rval;
    }
    else
    {
        std::vector< const MeshSet* > list;
        ErrorCode rval = recursive_get_sets( handle, seqman, &list );
        for( std::vector< const MeshSet* >::iterator i = list.begin(); i != list.end(); ++i )
            ( *i )->get_entities_by_type( tp, entities );
        return rval;
    }
}

ErrorCode MeshSetSequence::num_entities( const SequenceManager* seqman,
                                         EntityHandle handle,
                                         int& number,
                                         bool recursive ) const
{
    if( !recursive )
    {
        number = get_set( handle )->num_entities();
        return MB_SUCCESS;
    }
    else
    {
        Range range;
        ErrorCode result = get_entities( seqman, handle, range, true );
        number           = range.size();
        return result;
    }
}

ErrorCode MeshSetSequence::num_dimension( const SequenceManager* seqman,
                                          EntityHandle handle,
                                          int dimension,
                                          int& number,
                                          bool recursive ) const
{
    if( !recursive )
    {
        number = get_set( handle )->num_entities_by_dimension( dimension );
        return MB_SUCCESS;
    }
    else
    {
        Range range;
        ErrorCode result = get_dimension( seqman, handle, dimension, range, true );
        number           = range.size();
        return result;
    }
}

ErrorCode MeshSetSequence::num_type( const SequenceManager* seqman,
                                     EntityHandle handle,
                                     EntityType tp,
                                     int& number,
                                     bool recursive ) const
{
    if( !recursive )
    {
        number = get_set( handle )->num_entities_by_type( tp );
        return MB_SUCCESS;
    }
    else
    {
        Range range;
        ErrorCode result = get_type( seqman, handle, tp, range, true );
        number           = range.size();
        return result;
    }
}

ErrorCode MeshSetSequence::recursive_get_sets( EntityHandle start_set,
                                               const SequenceManager* seq_sets,
                                               std::vector< const MeshSet* >* sets,
                                               Range* set_handles,
                                               std::vector< EntityHandle >* set_vector )
{
    std::set< EntityHandle > visited;
    std::vector< EntityHandle > stack;
    stack.push_back( start_set );
    bool remove_start_set = true;
    while( !stack.empty() )
    {
        EntityHandle handle = stack.back();
        stack.pop_back();

        if( !visited.insert( handle ).second )
        {
            if( handle == start_set ) remove_start_set = false;
            continue;
        }

        const EntitySequence* seq;
        ErrorCode rval = seq_sets->find( handle, seq );
        if( MB_SUCCESS != rval ) return rval;

        const MeshSetSequence* mseq = reinterpret_cast< const MeshSetSequence* >( seq );
        const MeshSet* ms_ptr       = mseq->get_set( handle );
        if( sets ) sets->push_back( ms_ptr );

        Range tmp_range;
        ms_ptr->get_entities_by_type( MBENTITYSET, tmp_range );
        std::copy( tmp_range.begin(), tmp_range.end(), std::back_inserter( stack ) );
    }

    if( set_handles )
    {
        if( remove_start_set ) visited.erase( start_set );
        Range::iterator hint = set_handles->begin();
        std::set< EntityHandle >::iterator it;
        for( it = visited.begin(); it != visited.end(); ++it )
            hint = set_handles->insert( hint, *it, *it );
    }

    if( set_vector )
    {
        if( remove_start_set ) visited.erase( start_set );
        std::copy( visited.begin(), visited.end(), std::back_inserter( *set_vector ) );
    }

    return MB_SUCCESS;
}

ErrorCode MeshSetSequence::recursive_get_sets( EntityHandle start_set,
                                               SequenceManager* seq_sets,
                                               std::vector< MeshSet* >& sets )
{
    std::set< EntityHandle > visited;
    std::vector< EntityHandle > stack;
    stack.push_back( start_set );
    while( !stack.empty() )
    {
        EntityHandle handle = stack.back();
        stack.pop_back();

        if( !visited.insert( handle ).second ) continue;

        EntitySequence* seq;
        ErrorCode rval = seq_sets->find( handle, seq );
        if( MB_SUCCESS != rval ) return rval;

        MeshSetSequence* mseq = reinterpret_cast< MeshSetSequence* >( seq );
        MeshSet* ms_ptr       = mseq->get_set( handle );
        sets.push_back( ms_ptr );

        Range tmp_range;
        ms_ptr->get_entities_by_type( MBENTITYSET, tmp_range );
        std::copy( tmp_range.begin(), tmp_range.end(), std::back_inserter( stack ) );
    }

    return MB_SUCCESS;
}

ErrorCode MeshSetSequence::get_parent_child_meshsets( EntityHandle meshset,
                                                      const SequenceManager* seq_sets,
                                                      std::vector< EntityHandle >& results,
                                                      int num_hops,
                                                      SearchType link_type ) const
{
    ErrorCode result = MB_SUCCESS;
    std::vector< EntityHandle >::iterator i;
    const EntityHandle *tmp_array = 0, *end;
    EntityHandle s, e;
    int count = 0;
    size_t n;

    // Skip any meshsets already in input vector (yes, don't
    // get their children either even if num_hops would indicate
    // that we should.)  There is an exception to that if the
    // input meshset is in the list, which is handled by the order
    // of checks in the main loop below.
    std::set< EntityHandle > visited;
    for( i = results.begin(); i != results.end(); ++i )
        visited.insert( *i );

    // Two lists for breadth-first search
    std::vector< EntityHandle > lists[2];
    int index = 0;                      // which list to read from (write to lists[1-index])
    lists[index].push_back( meshset );  // begin with input set
                                        // loop for num_hops (or until no more sets)
    for( ; num_hops && !lists[index].empty(); --num_hops )
    {
        // for each set at the current num_hops
        for( i = lists[index].begin(); i != lists[index].end(); ++i )
        {
            // get meshset from handle
            const EntitySequence* seq;
            ErrorCode rval = seq_sets->find( *i, seq );
            if( MB_SUCCESS != rval ) return rval;
            const MeshSet* ms_ptr = reinterpret_cast< const MeshSetSequence* >( seq )->get_set( *i );

            switch( link_type )
            {
                case CONTAINED:
                    tmp_array = ms_ptr->get_contents( n );
                    end       = tmp_array + n;
                    if( ms_ptr->vector_based() )
                    {
                        for( ; tmp_array != end; ++tmp_array )
                            if( MBENTITYSET == TYPE_FROM_HANDLE( *tmp_array ) && visited.insert( *tmp_array ).second )
                                lists[1 - index].push_back( *tmp_array );
                    }
                    else
                    {
                        assert( n % 2 == 0 );
                        tmp_array = std::lower_bound( tmp_array, tmp_array + n, FIRST_HANDLE( MBENTITYSET ) );
                        // only part of first block is of type
                        if( ( end - tmp_array ) % 2 )
                        {
                            ++tmp_array;
                            s = FIRST_HANDLE( MBENTITYSET );
                            e = *tmp_array;
                            for( ; s <= e; ++s )
                                if( visited.insert( s ).second ) lists[1 - index].push_back( s );
                        }
                        while( tmp_array < end )
                        {
                            s = *tmp_array++;
                            e = *tmp_array++;
                            for( ; s <= e; ++s )
                                if( visited.insert( s ).second ) lists[1 - index].push_back( s );
                        }
                    }
                    continue;
                case PARENTS:
                    tmp_array = ms_ptr->get_parents( count );
                    break;
                case CHILDREN:
                    tmp_array = ms_ptr->get_children( count );
                    break;
            }

            // copy any parents/children we haven't visited yet into list
            for( end = tmp_array + count; tmp_array != end; ++tmp_array )
                if( visited.insert( *tmp_array ).second ) lists[1 - index].push_back( *tmp_array );
        }

        // iterate
        lists[index].clear();
        index = 1 - index;
        // append each level of sets to the output list.
        // note: to make a more useful search (e.g. get entities 3 hops away,
        // rather than entities up to and including 3 hops) move this outside
        // the loop, but then need to handle the get all (num_hops < 0) case
        // specially.
        std::copy( lists[index].begin(), lists[index].end(), std::back_inserter( results ) );
    }

    return result;
}

ErrorCode MeshSetSequence::get_parents( const SequenceManager* seqman,
                                        EntityHandle handle,
                                        std::vector< EntityHandle >& parents,
                                        int num_hops ) const
{
    if( num_hops == 1 )
    {
        int count;
        const EntityHandle* tmp_array = get_set( handle )->get_parents( count );
        if( parents.empty() )
        {
            parents.resize( count );
            std::copy( tmp_array, tmp_array + count, parents.begin() );
            return MB_SUCCESS;
        }
        else if( !count )
        {
            return MB_SUCCESS;
        }
    }

    if( num_hops > 0 )
        return get_parent_child_meshsets( handle, seqman, parents, num_hops, PARENTS );
    else
        return get_parent_child_meshsets( handle, seqman, parents, -1, PARENTS );
}

ErrorCode MeshSetSequence::get_children( const SequenceManager* seqman,
                                         EntityHandle handle,
                                         std::vector< EntityHandle >& children,
                                         int num_hops ) const
{
    if( num_hops == 1 )
    {
        int count;
        const EntityHandle* tmp_array = get_set( handle )->get_children( count );
        if( children.empty() )
        {
            children.resize( count );
            std::copy( tmp_array, tmp_array + count, children.begin() );
            return MB_SUCCESS;
        }
        else if( !count )
        {
            return MB_SUCCESS;
        }
    }

    if( num_hops > 0 )
        return get_parent_child_meshsets( handle, seqman, children, num_hops, CHILDREN );
    else
        return get_parent_child_meshsets( handle, seqman, children, -1, CHILDREN );
}

ErrorCode MeshSetSequence::get_contained_sets( const SequenceManager* seqman,
                                               EntityHandle handle,
                                               std::vector< EntityHandle >& contained,
                                               int num_hops ) const
{
    if( num_hops == 1 && contained.empty() )
    {
        return get_set( handle )->get_entities_by_type( MBENTITYSET, contained );
    }

    if( num_hops > 0 )
        return get_parent_child_meshsets( handle, seqman, contained, num_hops, CONTAINED );
    else
        return get_parent_child_meshsets( handle, seqman, contained, -1, CONTAINED );
}

ErrorCode MeshSetSequence::num_parents( const SequenceManager* seqman,
                                        EntityHandle handle,
                                        int& number,
                                        int num_hops ) const
{
    if( num_hops == 1 )
    {
        number = get_set( handle )->num_parents();
        return MB_SUCCESS;
    }

    std::vector< EntityHandle > parents;
    ErrorCode result = get_parents( seqman, handle, parents, num_hops );
    number           = parents.size();
    return result;
}

ErrorCode MeshSetSequence::num_children( const SequenceManager* seqman,
                                         EntityHandle handle,
                                         int& number,
                                         int num_hops ) const
{
    if( num_hops == 1 )
    {
        number = get_set( handle )->num_children();
        return MB_SUCCESS;
    }

    std::vector< EntityHandle > children;
    ErrorCode result = get_children( seqman, handle, children, num_hops );
    number           = children.size();
    return result;
}

ErrorCode MeshSetSequence::num_contained_sets( const SequenceManager* seqman,
                                               EntityHandle handle,
                                               int& number,
                                               int num_hops ) const
{
    if( num_hops == 1 )
    {
        number = get_set( handle )->num_entities_by_type( MBENTITYSET );
        return MB_SUCCESS;
    }

    std::vector< EntityHandle > contained;
    ErrorCode result = get_contained_sets( seqman, handle, contained, num_hops );
    number           = contained.size();
    return result;
}

}  // namespace moab
